package robot01;

import java.util.Scanner;
/*题目描述
机器人搬砖，一共有N堆砖存放在N个不同的仓库中，第i堆砖中有bricks[i]块砖头，要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格，
机器人一个小时中只能在一个仓库中搬砖，机器人的能量格每小时补充一次且能量格只在这一个小时有效，为使得机器人损耗最小化，尽量减小每次补充的能量格数。

为了保障在8小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。

备注:

1、无需考虑机器人补充能量格的耗时

2、无需考虑机器人搬砖的耗时

3、机器人每小时补充能量格只在这一个小时中有效。

输入描述
程序输入为"30 12 25 8 19"一个整数数组，数组中的每个数字代表第i堆砖的个数，每堆砖的个数不超过100

输出描述
输出在8小时内完成搬砖任务，机器人每小时最少需要充多少个能量格；如果8个小时内无论如何都完成不了任务，则输出"-1"
*/
public class Robot {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        int h = 8;
        if (nums.length > h){
            System.out.println(-1);
        } else {
            int result = minEatingSpeed(nums, h);
            System.out.println(result);
        }

    }

    // 计算花费在速度k的条件下，所花费的时间h的函数
    public static int calHourUsed(int[] nums, int k) {
        int hours = 0;
        for (int p : nums) {
            hours += Math.ceil((double) p / k);
        }
        return hours;
    }

    // 二分查找求解问题的函数
    public static int minEatingSpeed(int[] nums, int h) {
        // 左闭右开区间，right取最大的那一堆的值再+1
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        right += 1;
        // left和right相等时，区间消失，退出循环
        while (left < right) {
            // 花费时间太少，速度偏大，速度还可以减小，
            // 搜索区间向左折半，right可以向左移动
            int mid = left + (right - left) / 2;
            if (calHourUsed(nums, mid) <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
        // 返回left或right均可
        return left;
    }
}

